﻿//迷宫中离入口最近的出口(medium): https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/description/
class Solution {
public:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool vis[110][110];
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m=maze.size(),n=maze[0].size();
        int step=0;
        queue<pair<int,int>> q;
        q.push({entrance[0],entrance[1]});
        vis[entrance[0]][entrance[1]]=true;
        while(!q.empty())
        {
            int size=q.size();
            step++;
            while(size--)
            {
                auto [a,b]=q.front();
                q.pop();
                for(int k=0;k<4;k++)
                {
                    int x=a+dx[k],y=b+dy[k];
                    if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&maze[x][y]=='.')
                    {
                        if(x==0||x==m-1||y==0||y==n-1)
                        {
                            return step;
                        }
                        q.push({x,y});
                        vis[x][y]=true;
                    }
                }
            }
        }
        return -1;
    }
};
